The invention relates to a process for performing a finite field multiplication of a first Galois element a represented by a bit vector a0 . . . an−1 in a first input register, to be multiplied by a second Galois element b represented by a bit vector b0 . . . bn−1 in a second input register in a digital Galois multiplier (MUL), the Galois elements a and b being members of a Galois field GF 2n described by an irreducible polynomial PR having a bit representation PR0 . . . PRn.
In finite field multiplication of Galois elements, it is premised that the basic arithmetical operation in digital signal processing is specified in general by:   y  =            ∑              i        =        0            n        ⁢                  x        i            *              a        i            Many algorithms can be reduced in essence to this folded sum, or arithmetically speaking, the summation across products. Usually in digital signal processing, these algorithms, e.g. in digital signal processors (DSP), are accelerated by the realization of a hard-wired hardware circuits implementing this summation of products. Such subassemblies are commonly referred to as multipliers (MUL).
If in this multiplier the arithmetic is applied in residue class fields with their modulo operation, use is made of a Galois MUL performing a finite field multiplication, in that in each line of the multiplier, first a partial product a×bi (i=0 to n−1) is formed. Then the partial product is added to the sum of the preceding lines, before the modulo operation is performed. This is done by adding bit places PR0 . . . PRn−1 to the sums previously computed, in accordance with an overflow occurring in the preceding line.
The invention relates further to one circuit apparatus each for carrying out the above-mentioned process according to claims 1 to 3, and to one circuit apparatus in which a Galois multiplier accumulator (MAC) is arranged, in which each of the said circuit apparatuses is contained.
A Galois MUL of cellular structure was described in “A Cellular Array Multiplier for GF(2m),” IEEE Transactions on Computers, Dec. 1971, 1573–1578, by B. A. Laws and C. K. Rushforth. In “Efficient Semisystolic Architectures for Finite Field Arithmetic,” IEEE Transactions on Very Large-Scale Integration (VLSI) Systems, vol. 6 no. 1, Mar. 1988, pp. 101–113, Surendra K. Jain, Leilei Song and Keshab K. Parhi tabulate various algorithms for the realization of Galois multipliers and their representation in circuitry.
A disadvantage of the realizations previously specified is that they possess a high ‘logical depth,’ i.e. a multitude of gates to be traversed in succession, and therefore, long signal transit times occur upon their implementation in finite field multiplication.
The object of the invention is to accelerate finite field multiplication.